Fraction to recurring decimal

Time: O(LogN); Space: O(1); medium

Note:

  • N is the length of result strings

Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.

If the fractional part is repeating, enclose the repeating part in parentheses.

Example1:

Input: numerator = 1, denominator = 2

Output: “0.5”

Example2:

Input: numerator = 2, denominator = 1

Output: “2”

Example3:

Input: numerator = 2, denominator = 3

Output: “0.(6)”

Hints:

  1. No scary math, just apply elementary math knowledge. Still remember how to perform a long division?

  2. Try a long division on 4/9, the repeating part is obvious. Now try 4/333. Do you see a pattern?

  3. Notice that once the remainder starts repeating, so does the divided result.

  4. Be wary of edge cases! List out as many test cases as you can think of and test your code thoroughly.

[5]:

class Solution1(object):
    def fractionToDecimal(self, numerator, denominator):
        """
        :type numerator: int
        :type denominator: int
        :rtype: str
        """
        result = ""
        if (numerator > 0 and denominator < 0) or (numerator < 0 and denominator > 0):
            result = "-"

        dvd, dvs = abs(numerator), abs(denominator)
        result += str(dvd // dvs)
        dvd %= dvs

        if dvd > 0:
            result += "."

        lookup = {}
        while dvd and dvd not in lookup:
            lookup[dvd] = len(result)
            dvd *= 10
            result += str(dvd // dvs)
            dvd %= dvs

        if dvd in lookup:
            result = result[:lookup[dvd]] + "(" + result[lookup[dvd]:] + ")"

        return result

[15]:

s = Solution1()
numerator = 1
denominator = 2
assert s.fractionToDecimal(numerator, denominator) == "0.5"

numerator = 2
denominator = 1
assert s.fractionToDecimal(numerator, denominator) == "2"

numerator = 2
denominator = 3
assert s.fractionToDecimal(numerator, denominator) == "0.(6)"

numerator = 1
denominator = 9
assert s.fractionToDecimal(numerator, denominator) == "0.(1)"

numerator = 22
denominator = 2
assert s.fractionToDecimal(numerator, denominator) == "11"

numerator = -22
denominator = -2
assert s.fractionToDecimal(numerator, denominator) == "11"